class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        return max(rob1(2, n - 2, nums) + nums[0], rob1(1, n - 1, nums));
    }

    int rob1(int l, int r, vector<int>& nums) {
        if (l > r) return 0;
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n, 0);
        f[l] = nums[l];
        for (int i = l + 1; i <= r; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[r], g[r]);
    }
};